﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Globalization;

namespace Platform.LanguageProcessing
{

	/// <summary>
	/// Dicionário de palavras
	/// </summary>
	/// <typeparam name="TValue"></typeparam>
	public sealed class WordDictionary<TValue> : IDictionary<string,TValue>
	{
		private const int DigitCount = 10;
		private const int LetterCount = 26;
		private const int AccCount = 23;
		private const int AccUCount = 5;
		private const int TableSize = DigitCount + LetterCount + AccCount + AccUCount;

		private const int ZeroCode = ( int )'0';
		private const int UpperA_Code = ( int )'A' - DigitCount;
		private const int LowerA_Code = ( int )'a' - DigitCount;
		private const int UpperAccA_Code = 192 - DigitCount - LetterCount;
		private const int LowerAccA_Code = 224 - DigitCount - LetterCount;
		private const int UpperAccU_Code = 217 - DigitCount - LetterCount - AccCount;
		private const int LowerAccU_Code = 249 - DigitCount - LetterCount - AccCount;
	
		
		private WordNode root = new WordNode();
		private int count = 0;


		public WordDictionary()
		{ }

		/// <summary>
		/// 
		/// </summary>
		/// <returns></returns>
		public ICollection<KeyValuePair<string, TValue>> ToCollection()
		{
			if ( this.count == 0 )
				return new List<KeyValuePair<string, TValue>>();

			// Conjunto de palavras e valores
			List<KeyValuePair<string, TValue>> result = new List<KeyValuePair<string, TValue>>();

			Stack<Tuple<char[], WordNode[]>> nodes = new Stack<Tuple<char[], WordNode[]>>();
			nodes.Push( new Tuple<char[], WordNode[]>( new char[] { }, this.root.letters ) );

			//
			while ( nodes.Count > 0 )
			{
				var pair = nodes.Pop();

				// prefixo
				char[] buffer = new char[ pair.Item1.Length + 1 ];
				int lastChar = buffer.Length - 1;
				pair.Item1.CopyTo( buffer, 0 );

				// Procura em todas as letras desse nodo
				for ( int index = 0; index < TableSize; index++ )
				{
					var node = pair.Item2[ index ];
					buffer[ lastChar ] = NodeChar( index );

					// Encontrou uma palavra
					if ( node.hasValue )
					{
						result.Add( new KeyValuePair<string, TValue>( new String( buffer ), node.Value ) );
					}

					// Há mais letras abaixo desse nodo
					if ( node.letters != null )
					{
						nodes.Push( new Tuple<char[], WordNode[]>( buffer, node.letters ) );

						buffer = new char[ pair.Item1.Length + 1 ];
						pair.Item1.CopyTo( buffer, 0 );
					}
				}
			}
			return result;
		}

		/// <summary>
		/// Realiza a navegação pela árvore de caracteres formado pelo dicionário de palavras
		/// </summary>
		/// <param name="path">Palavra que é utilizada para navegar pelos nodos da árvore</param>
		/// <param name="addIfNeeds">Adiciona o valor <paramref name="toAdd"/> e os nodos necessários na árvore de caracteres</param>
		/// <param name="toAdd">Valor que será adicionado na árvore</param>
		/// <param name="node">Retorna o nó procurado ou o último nó encontrado pela navegação <paramref name="path"/>.</param>
		/// <returns></returns>
		private bool TryNavigateBy( string path, bool addIfNeeds, TValue toAdd, out WordNode node )
		{
			int cIndex = 0;
			int nodeIndex = 0;
			int stopAt = path.Length;
			WordNode[] lastRow = null;
			WordNode[] cCharRow = this.root.letters;

			// Percorre até encontrar um node que não tenha filhos, ou até o final da palavra "path"
			while ( cIndex < stopAt
				&& cCharRow != null )
			{
				lastRow = cCharRow;
				cCharRow = cCharRow[ nodeIndex = NodeIndex( path[ cIndex++ ] ) ].letters;
			}

			if ( addIfNeeds )
			{
				// Se parou no meio da palavra "path", adiciona os caracteres restantes
				if ( cCharRow == null )
				{
					// Precisa voltar somente um caracter da palavra, pois chegou no final
					// mas não tem a última letra
					if ( lastRow == null )
						cCharRow = this.root.letters = WordNode.NewVector();
					else
					{
						cCharRow = lastRow;
						cIndex--;
					}

					//
					stopAt--;	// Na última letra não precisa criar um vetor
					while ( cIndex < stopAt )
					{
						cCharRow
							= cCharRow[ NodeIndex( path[ cIndex++ ] ) ].letters
							= WordNode.NewVector();
					}

					nodeIndex = NodeIndex( path[ cIndex ] );
				}
				else
				{
					// Não precisa recalcular "nodeIndex", já vai estar pronto para utilizar
					// nodeIndex = NodeIndex( path[ cIndex ] );
					cCharRow = lastRow;
				}

				this.count++;

				// Atribui o valor
				cCharRow[ nodeIndex ].Value = toAdd;
				node = cCharRow[ nodeIndex ];
				return true;
			}
			else if ( cIndex == stopAt )	// Se chegou no final da palavra, verifica se tem valor
			{
				node = lastRow[ nodeIndex ];
				return node.hasValue;
			}
			else if ( lastRow == null )
			{
				node = default( WordNode );
				return false;
			}
			// Não encontrou a palavra inteira na árvore, então retorna o último nodo, se tiver nodos na árvore
			else
			{
				node = lastRow[ nodeIndex ];
				return false;
			}
		}


		/// <summary>
		/// Retorna o último nodo que contém a palavra <paramref name="word"/>
		/// </summary>
		/// <param name="word"></param>
		/// <returns></returns>
		public KeyValuePair<string, TValue> GetBestMatch( string word )
		{
			int cIndex = 0;
			int len = word.Length;
			WordNode node = this.root;

			while ( cIndex < len
				&& node.letters != null )
			{
				node = node.letters[ NodeIndex( word[ cIndex ] ) ];
				cIndex++;
			}

			if ( node.hasValue )
				return new KeyValuePair<string, TValue>( word.Substring( 0, cIndex ), node.Value );
			else
				return new KeyValuePair<string, TValue>( word.Substring( 0, cIndex - 1 ), default( TValue ) );
		}


		/// <summary>
		/// Retorna todos os nodos que possuem valores, mesmo se tiverem null
		/// </summary>
		/// <param name="word"></param>
		/// <returns></returns>
		public IEnumerable<KeyValuePair<string, TValue>> GetAnagrams( string word )
		{
			int cIndex = 0;
			int len = word.Length;
			WordNode current = this.root;

			while ( cIndex < len
				&& current.letters != null )
			{
				//current = current.GetChildren( word[ cIndex ] );
				current = current.letters[ NodeIndex( word[ cIndex++ ] ) ];

				if ( current.hasValue )
				{
					yield return new KeyValuePair<string, TValue>( word.Substring( 0, cIndex ), current.Value );
				}
			}
		}

		#region IDictionary<string,TValue> Members

		public void Add( string key, TValue value )
		{
			WordNode node;
			this.TryNavigateBy( key, true, value, out node );
		}

		public bool ContainsKey( string key )
		{
			WordNode node;
			return this.TryNavigateBy( key, false, default( TValue ), out node );
		}

		public ICollection<string> Keys
		{
			get { return this.ToCollection().Select( p => p.Key ).ToList(); }
		}

		public bool Remove( string key )
		{
			throw new NotImplementedException();
		}

		public bool TryGetValue( string key, out TValue value )
		{
			WordNode node;

			if ( this.TryNavigateBy( key, false, default( TValue ), out node ) )
			{
				value = node.Value;
				return true;
			}
			else
			{
				value = default( TValue );
				return false;
			}
		}

		public ICollection<TValue> Values
		{
			get
			{
				return this.ToCollection().Select( p => p.Value ).ToList();
			}
		}

		public TValue this[ string key ]
		{
			get
			{
				WordNode node;
				if ( this.TryNavigateBy( key, false, default( TValue ), out node )
					&& node.hasValue )
				{
					return node.Value;
				}
				else
				{
					throw new InvalidOperationException();
				}
			}
			set
			{
				WordNode node;
				this.TryNavigateBy( key, true, value, out node );
			}
		}

		#endregion

		#region ICollection<KeyValuePair<string,TValue>> Members

		public void Add( KeyValuePair<string, TValue> item )
		{
			this.Add( item.Key, item.Value );
		}

		public void Clear()
		{
			this.root = new WordNode();
		}

		public bool Contains( KeyValuePair<string, TValue> item )
		{
			WordNode node;

			return this.TryNavigateBy( item.Key, false, default( TValue ), out node )
				&& Object.Equals( item.Value, node.Value );
		}

		public void CopyTo( KeyValuePair<string, TValue>[] array, int arrayIndex )
		{
			throw new NotImplementedException();
		}

		public int Count
		{
			get { return this.count; }
		}

		public bool IsReadOnly
		{
			get { return false; }
		}

		public bool Remove( KeyValuePair<string, TValue> item )
		{
			throw new NotImplementedException();
		}

		#endregion

		#region IEnumerable<KeyValuePair<string,TValue>> Members

		public IEnumerator<KeyValuePair<string, TValue>> GetEnumerator()
		{
			return this.ToCollection().GetEnumerator();
		}

		#endregion

		#region IEnumerable Members

		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
		{
			return this.GetEnumerator();
		}

		#endregion


		private static int NodeIndex( char c )
		{
			return ( int )c - DeltaIndex( c );
		}

		private static char NodeChar( int index )
		{
			if ( index < DigitCount )
			{
				return ( char )( index + ZeroCode );
			}
			else if ( index < LetterCount + DigitCount )
			{
				return ( char )( index + LowerA_Code );
			}
			else if ( index < AccCount + LetterCount + DigitCount )
			{
				return ( char )( index + LowerAccA_Code );
			}
			else
			{
				return ( char )( index + LowerAccU_Code );
			}
		}

		private static int DeltaIndex( char c )
		{
			switch ( c )
			{
				#region [ Digit ]
				case '0':
				case '1':
				case '2':
				case '3':
				case '4':
				case '5':
				case '6':
				case '7':
				case '8':
				case '9':
				#endregion
					return ZeroCode;

				#region [ Lower a-z ]
				case 'a':
				case 'b':
				case 'c':
				case 'd':
				case 'e':
				case 'f':
				case 'g':
				case 'h':
				case 'i':
				case 'j':
				case 'k':
				case 'l':
				case 'm':
				case 'n':
				case 'o':
				case 'p':
				case 'q':
				case 'r':
				case 's':
				case 't':
				case 'u':
				case 'v':
				case 'w':
				case 'x':
				case 'y':
				case 'z':
				#endregion
					return LowerA_Code;

				#region [ Upper A-Z ]
				case 'A':
				case 'B':
				case 'C':
				case 'D':
				case 'E':
				case 'F':
				case 'G':
				case 'H':
				case 'I':
				case 'J':
				case 'K':
				case 'L':
				case 'M':
				case 'N':
				case 'O':
				case 'P':
				case 'Q':
				case 'R':
				case 'S':
				case 'T':
				case 'U':
				case 'V':
				case 'W':
				case 'X':
				case 'Y':
				case 'Z':
				#endregion
					return UpperA_Code;

				#region [ Acc a-o ]
				case 'À':
				case 'Á':
				case 'Â':
				case 'Ã':
				case 'Ä':
				case 'Å':
				case 'Æ':
				case 'Ç':
				case 'È':
				case 'É':
				case 'Ê':
				case 'Ë':
				case 'Ì':
				case 'Í':
				case 'Î':
				case 'Ï':
				case 'Ð':
				case 'Ñ':
				case 'Ò':
				case 'Ó':
				case 'Ô':
				case 'Õ':
				case 'Ö':
				case '×':
				#endregion
					return UpperAccA_Code;
				
				#region [ Acc Lower a-o ]
				case 'à':
				case 'á':
				case 'â':
				case 'ã':
				case 'ä':
				case 'å':
				case 'æ':
				case 'ç':
				case 'è':
				case 'é':
				case 'ê':
				case 'ë':
				case 'ì':
				case 'í':
				case 'î':
				case 'ï':
				case 'ð':
				case 'ñ':
				case 'ò':
				case 'ó':
				case 'ô':
				case 'õ':
				case 'ö':
				#endregion
					return LowerAccA_Code;

				#region [ Acc Upper u ]
				case 'Ù':
				case 'Ú':
				case 'Û':
				case 'Ü':
				case 'Ý':
				case 'Þ':
				case 'ß':
				#endregion
					return UpperAccU_Code;

				#region [ Acc Lower u ]
				case 'ù':
				case 'ú':
				case 'û':
				case 'ü':
				case 'ý':
				#endregion
					return LowerAccU_Code;

				default:
					return 0;
			}
		}


		#region [ struct WordNode ]

		/// <summary>
		/// Estrutura que representa um nodo da árvore
		/// </summary>
		internal struct WordNode
		{
			internal WordNode[] letters;
			internal bool hasValue;
			private TValue value;


			/// <summary>
			/// Obtém o valor armazenado no nodo
			/// </summary>
			internal TValue Value
			{
				get { return this.value; }
				set
				{
					this.value = value;
					this.hasValue = true;
				}
			}
			
			internal static WordNode[] NewVector()
			{
				return new WordNode[ TableSize ];
			}
		}

		#endregion
	}
}
